package Datastruct.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

    //顶点元素
    private ArrayList<String> vertexList;
    //邻接矩阵
    private int[][] edges;
    private int edgesNum;
    private boolean[] isSelect;

    public Graph(int x) {
        this.vertexList = new ArrayList<String>(x);
        this.edges = new int[x][x];
        this.isSelect = new boolean[x];
    }

    //插入顶点的方法
    public void insertVertex(String vertex) {
        this.vertexList.add(vertex);
    }

    //添加图边
    public void insertEdges(int x, int y, int w) {
        edges[x][y] = w;
        edges[y][x] = w;

        //添加边的数量
        edgesNum++;

    }

    //返回顶点的数量
    public int getVertextSize() {
        return this.vertexList.size();
    }

    //返回边的数量
    public int getEdgesSize() {
        return this.edgesNum;
    }

    //获取顶点的权值 ,x,y坐标下权值
    public int getWeight(int x, int y) {
        return this.edges[x][y];
    }

    //输出邻接矩阵的图案
    public void showList() {
        for (int[] arr : edges) {
            System.out.println(Arrays.toString(arr));
        }
    }

    //给定一个索引顶点位置，查找当前索引的第一个邻接点
    //如果存在返回索引位置
    //不存在返回-1
    public int getFirstVertex(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    //根据给定的坐标，获取下一个邻接点
    public int getNextVertext(int x, int y) {
        for (int i = y + 1; i < vertexList.size(); i++) {
            if (edges[x][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    //访问的顶点
    public String getValueIndex(int i) {
        return this.vertexList.get(i);
    }

    //深度优先算法
    public void dfs(boolean[] isSelecct, int i) {
        System.out.print(getValueIndex(i));
        //表示已经被访问的顶点
        isSelecct[i] = true;
        //获取第一个邻接顶点
        int w = getFirstVertex(i);
        while (w != -1) {
            if (!isSelecct[w]) {
                dfs(isSelecct, w);
            }
            //被访问过
            w = getNextVertext(i, w);
        }
    }

    public void dfs() {
        for (int i = 0; i < getVertextSize(); i++) {
            if (!isSelect[i]) {
                dfs(isSelect, i);
            }
        }
    }


    //广度优先算法
    public void bfs(boolean[] isSelect, int i) {
        //取出头结点
        int u;
        //第一个邻接点
        int w;

        //创建队列
        LinkedList queue = new LinkedList();
        System.out.print(getValueIndex(i));

        isSelect[i] = true;
        queue.addLast(i);

        while (!queue.isEmpty()) {
            u = (Integer) queue.removeFirst();
            w = getFirstVertex(u);
            while (w != -1) {
                if (!isSelect[w]) {
                    System.out.print(getValueIndex(w));
                    isSelect[w] = true;
                    queue.addLast(w);
                }
                w = getNextVertext(u, w);
            }
        }
    }

    //
    public void bfs() {
        for (int i = 0; i < getEdgesSize(); i++) {
            if (!isSelect[i]) {
                bfs(isSelect, i);
            }
        }
    }


}
